#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define SYMBOL       1
#define VECTOR       2
#define PAIR         16
#define COMMA        symbol("COMMA")
#define COMMA_AT     symbol("COMMA_AT")
#define BQ_LIST      symbol("BQ-LIST")
#define BQ_APPEND    symbol("BQ-APPEND")
#define BQ_QUOTE     symbol("BQ-QUOTE")

struct pair {
    struct sexp *car;
    struct sexp *cdr;
};

struct sexp {
    int type;
    union {
        char* atom;
        struct pair *pr;
    };
};

static struct sexp *nil;

struct sexp *bq_process(struct sexp *x);
struct sexp *bq_remove_tokens(struct sexp *x);
struct sexp *bracket(struct sexp *x);

int strcmp(const char *str1,const char *str2)
{
    while(*str1 == *str2)
    {
        if(*str1 == '\0')
            return 0;

        str1++;
        str2++;
    }
    return *str1 - *str2;
}


struct sexp *bq_completely_process(struct sexp *x) {
    struct sexp *raw_result = bq_process(x);
    return bq_remove_tokens(raw_result);
}

struct sexp *nreconc(struct sexp **lst, struct sexp *tail) {
    struct sexp *p = *lst;
    struct sexp *m = *lst;
    struct sexp *n = *lst;

    if (*lst == nil) {
        *lst = tail;
        return tail;
    }

    p = p->pr->cdr;
    while (p != nil) {
        m = p;
        p = p->pr->cdr;
        m->pr->cdr = n;
        n = m;
    }
    (*lst)->pr->cdr = tail;
    *lst = m;
    return m;
}

struct sexp *symbol(char* string) {
    struct sexp *s = (struct sexp *)malloc(sizeof(struct sexp));
    s->type = SYMBOL;
    s->atom = string;
}

struct sexp *vector_to_list(struct sexp *x) {
    return x; //todo
}

struct sexp *cons(struct sexp *a1, struct sexp *a2) {
    struct sexp *c = (struct sexp *)malloc(sizeof(struct sexp));
    c->type = PAIR;
    c->pr = (struct pair *)malloc(sizeof(struct pair));
    c->pr->car = a1;
    c->pr->cdr = a2;
    return c;
}

struct sexp *list_1(struct sexp *a1) {
    struct sexp *lst = (struct sexp *)malloc(sizeof(struct sexp));
    lst->type = PAIR;
    lst->pr = (struct pair *)malloc(sizeof(struct pair));
    lst->pr->car = a1;
    lst->pr->cdr = nil;
    return lst;
}

struct sexp *list_2(struct sexp *a1, struct sexp *a2) {
    struct sexp *lst = (struct sexp *)malloc(sizeof(struct sexp));
    lst->type = PAIR;
    lst->pr = (struct pair *)malloc(sizeof(struct pair));
    lst->pr->car = a1;
    lst->pr->cdr = (struct sexp *)malloc(sizeof(struct sexp));
    lst->pr->cdr->type = PAIR;
    lst->pr->cdr->pr = (struct pair *)malloc(sizeof(struct pair));
    lst->pr->cdr->pr->car = a2;
    lst->pr->cdr->pr->cdr = nil;
    return lst;
}

int equals_atom(struct sexp *a, struct sexp *b) {
    return (a->type != PAIR && b->type != PAIR && strcmp(a->atom, b->atom) == 0);
}

struct sexp *bq_process(struct sexp *x) {
    void *result;
    if (x->type != PAIR) {
        if (x->type == VECTOR) {
            result = list_2(symbol("list-to-vector"), bq_process(vector_to_list(x)));
        }
        else {
            result = list_2(BQ_QUOTE, x);
        }
        return result;
    }
    else if (equals_atom(x->pr->car, symbol("backquote"))) {
        return bq_process(bq_completely_process(x->pr->cdr->pr->car)); //car(cdr(x))
    }
    else if (equals_atom(x->pr->car, COMMA)) {
        return x->pr->cdr->pr->car;
    }
    else if (equals_atom(x->pr->car, COMMA_AT)) {
        //error(",@~S after `", x->pr->cdr->pr->car);
        perror("COMMA_AT after BQ_QUOTE");
        exit(0);
    }
    else {
        struct sexp *p = x;
        struct sexp *q = nil;

        while(1) {
            if (p->type != PAIR) {
                return cons(BQ_APPEND, nreconc(&q, list_1(list_2(BQ_QUOTE, p))));
            }
            if (equals_atom(p->pr->car, COMMA)) {
                if (p->pr->cdr->pr->cdr == nil) {
                    //error("Malformed ,~S", p);
                    perror("Malformed");
                    exit(0);
                }
                return cons(BQ_APPEND, nreconc(&q, list_1(p->pr->cdr->pr->car)));
            }
            if (equals_atom(p->pr->car, COMMA_AT)) {
                //error("Dotted ,@~S", p);
                perror("Dotted");
                exit(0);
            }

            q = cons(bracket(p->pr->car), q);
            p = p->pr->cdr;
        }
    }
}

int equals(struct sexp *a, struct sexp *b) {
    if (a == nil && b == nil) {
        return 1;
    }
    if (a == nil || b == nil) {
        return 0;
    }
    if (a->type != b->type) {
        return 0;
    }
    if (a->type != PAIR) {
        return strcmp(a->atom, b->atom) == 0;
    }
    else {
        return equals(a->pr->car, b->pr->car) && equals(a->pr->cdr, b->pr->cdr);
    }
}

// jalr $v0
struct sexp *maptree(struct sexp* (*fn)(struct sexp *x), struct sexp *x) {
    if (x->type != PAIR) {
        return fn(x);
    }
    else {
        struct sexp *a = fn(x->pr->car);
        struct sexp *d = maptree(fn, x->pr->cdr);

        if (equals(a, x->pr->car) && equals(d, x->pr->cdr)) {
            return x;
        }
        else {
            return cons(a, d);
        }
    }
}

struct sexp * bq_remove_tokens(struct sexp * x) {
    if (equals_atom(x, BQ_LIST)) {
        return symbol("list");
    }
    else if (equals_atom(x, BQ_APPEND)) {
        return symbol("append");
    }
    else if (equals_atom(x, BQ_QUOTE)) {
        return symbol("quote");
    }
    else if (x->type != PAIR) {
        return x;
    }
    else if (equals_atom(x->pr->car, BQ_LIST) && x->pr->cdr->pr->cdr->type == PAIR && x->pr->cdr->pr->cdr->pr->cdr == nil) {
        return cons(symbol("cons"), maptree(bq_remove_tokens, x->pr->cdr));
    }
    else {
        return maptree(bq_remove_tokens, x);
    }
}

struct sexp *bracket(struct sexp *x) {
    if (x->type != PAIR) {
        return list_2(BQ_LIST, bq_process(x));
    }
    else if (equals_atom(x->pr->car, COMMA)) {
        return list_2(BQ_LIST, x->pr->cdr->pr->car);
    }
    else if (equals_atom(x->pr->car, COMMA_AT)) {
        return x->pr->cdr->pr->car;
    }
    else {
        return list_2(BQ_LIST, bq_process(x));
    }
}

void print_sexp(struct sexp *exp) {
    struct sexp *t = exp;

    if (exp->type == SYMBOL) {
        printf("%s", exp->atom);
    } else if  (exp->type == PAIR) {
        printf("( ");
        while (1) {
            if (t->type != PAIR) break;
            if (t->pr->cdr == nil) break;
            if (t->type == PAIR) {
                print_sexp(t->pr->car);
            }
            else {
                print_sexp(t);
            }

            if (t->type == PAIR) {
                if (t->pr->cdr->type != PAIR) {
                    printf(" . ");
                } else {
                    printf(" ");
                }
            }
            t = t->pr->cdr;
        }
        if (t->type == PAIR) {
            print_sexp(t->pr->car);
        }
        else {
            print_sexp(t);
        }
        printf(" )");
    } else if  (exp == nil) {
        printf("()");
    } else {
        perror("error!");
    }
}

//bq-process: 1
void test1() {
    struct sexp *s = (struct sexp *)malloc(sizeof(struct sexp));
    s->type = SYMBOL;
    s->atom = "1";
    print_sexp(s);
    print_sexp(bq_completely_process(s));
}

//bq-process: (1 2 3)
void test2() {
    struct sexp *a1 = (struct sexp *)malloc(sizeof(struct sexp));
    a1->type = SYMBOL;
    a1->atom = "1";
    struct sexp *a2 = (struct sexp *)malloc(sizeof(struct sexp));
    a2->type = SYMBOL;
    a2->atom = "2";
    struct sexp *a3 = (struct sexp *)malloc(sizeof(struct sexp));
    a3->type = SYMBOL;
    a3->atom = "3";

    struct sexp *s = cons(a1, cons(a2, cons(a3, nil)));
    print_sexp(s);
    print_sexp(bq_completely_process(s));
}

//bq-process: (1 ,X 2)  (1 (comma X) 2)
void test3() {
    struct sexp *a1 = (struct sexp *)malloc(sizeof(struct sexp));
    a1->type = SYMBOL;
    a1->atom = "1";
    struct sexp *a2 = (struct sexp *)malloc(sizeof(struct sexp));
    a2->type = SYMBOL;
    a2->atom = "X";
    struct sexp *a3 = (struct sexp *)malloc(sizeof(struct sexp));
    a3->type = SYMBOL;
    a3->atom = "2";

    struct sexp *s = cons(a1, cons(list_2(COMMA, a2), cons(a3, nil)));
    print_sexp(s);
    print_sexp(bq_completely_process(s));
}

//bq-process: (1 ,@X 2)  (1 (comma-at X) 2)
void test4() {
    struct sexp *a1 = (struct sexp *)malloc(sizeof(struct sexp));
    a1->type = SYMBOL;
    a1->atom = "1";
    struct sexp *a2 = (struct sexp *)malloc(sizeof(struct sexp));
    a2->type = SYMBOL;
    a2->atom = "X";
    struct sexp *a3 = (struct sexp *)malloc(sizeof(struct sexp));
    a3->type = SYMBOL;
    a3->atom = "2";

    struct sexp *s = cons(a1, cons(list_2(COMMA_AT, a2), cons(a3, nil)));
    print_sexp(s);
    print_sexp(bq_completely_process(s));
}

//bq-process: (1 (2 ,X 3) 4)   其中 ,X 嵌套在第二层列表中.
void test5() {
    struct sexp *a1 = (struct sexp *)malloc(sizeof(struct sexp));
    a1->type = SYMBOL;
    a1->atom = "1";
    struct sexp *a2 = (struct sexp *)malloc(sizeof(struct sexp));
    a2->type = SYMBOL;
    a2->atom = "2";
    struct sexp *a3 = (struct sexp *)malloc(sizeof(struct sexp));
    a3->type = SYMBOL;
    a3->atom = "3";
    struct sexp *a4 = (struct sexp *)malloc(sizeof(struct sexp));
    a4->type = SYMBOL;
    a4->atom = "4";
    struct sexp *a5 = (struct sexp *)malloc(sizeof(struct sexp));
    a5->type = SYMBOL;
    a5->atom = "X";

    struct sexp *s = cons(a1, cons(cons(a2, cons(list_2(COMMA, a5), cons(a3, nil))), cons(a4, nil)));
    print_sexp(s);
    print_sexp(bq_completely_process(s));
}

//bq-process: (1 2 . 3)
void test6() {
    struct sexp *a1 = (struct sexp *)malloc(sizeof(struct sexp));
    a1->type = SYMBOL;
    a1->atom = "1";
    struct sexp *a2 = (struct sexp *)malloc(sizeof(struct sexp));
    a2->type = SYMBOL;
    a2->atom = "2";
    struct sexp *a3 = (struct sexp *)malloc(sizeof(struct sexp));
    a3->type = SYMBOL;
    a3->atom = "3";

    struct sexp *s = cons(a1, cons(a2, a3));
    print_sexp(s);
    print_sexp(bq_completely_process(s));
}

int main() {
    nil = (struct sexp *)malloc(sizeof(struct sexp));
    nil->type = -1;
    nil->atom = "";

    test6();


    return 0;
}

